/*------------------------------------------------------------------------*/
/*  File: cluster_editing.c                                               */
/*  Version 1.0                                                           */
/*------------------------------------------------------------------------*/
/*  Written for Software Project Class.                                   */
/*  Based uopn qpex1.c                                                    */
/*  Permission is expressly granted to use this example in the            */
/*  course of developing applications that use ILOG products.             */
/*------------------------------------------------------------------------*/

/* cluster_editing.c - Entering and optimizing cluster editing integer linear programming problem */
#include "cluster_editing.h"

#define IS_VALUE_1(X) ((1 - X) < 0.00001)

/* This routine initializes the CPLEX environment, sets screen as an output for cplex errors and notifications,
   and sets parameters for CPLEX. It calls for a mixed integer program solution and frees the environment.
   It then create the clustering structure of the graph, and populates the score and averageWeights of edges.
*/
int cluster(graph* gr, char* probname, double* score, double* avgWeightWithinClusters, double* avgWeightBetweenClusters)
{
   CPXENVptr p_env = NULL;
   CPXLPptr  p_lp = NULL;
   int       status=0;
   double*	 indicators = NULL;
   
   p_env = CPXopenCPLEX (&status);
   if ( p_env == NULL ) {
   char  errmsg[1024];
      fprintf (stderr, "Error: Could not open CPLEX environment.\n");
      CPXgeterrorstring (p_env, status, errmsg);
      fprintf (stderr, "%s", errmsg);
      goto TERMINATE;
   }
   status = CPXsetintparam (p_env, CPX_PARAM_SCRIND, CPX_ON);
   if ( status ) {
      fprintf (stderr, 
		  "Error: Failure to turn on screen indicator, error %d.\n", status);
      goto TERMINATE;
   }
   p_lp = CPXcreateprob (p_env, &status, probname);
   if ( p_lp == NULL ) {
      fprintf (stderr, "Error: Failed to create problem.\n");
      goto TERMINATE;
   }
   status = GenerateCPLEXProblem(&p_env, &p_lp, gr);
   if ( status ) {
         goto TERMINATE;
   }
   status = CPXwriteprob (p_env, p_lp, probname, NULL);
   if ( status ) {
	   fprintf (stderr, "Error: Failed to write LP to disk.\n");
	   goto TERMINATE;
   }
    
   status = CPXmipopt (p_env, p_lp);
   if ( status ) {
      fprintf (stderr, "Error: Failed to optimize problem.\n");
      goto TERMINATE;
   }
   status = CPXwriteprob (p_env, p_lp, probname, NULL);
   if ( status ) {
	   fprintf (stderr, "Error: Failed to write LP to disk.\n");
	   goto TERMINATE;
   }

   indicators = malloc(sizeof(double)*OVER_2(gr->numofVertices));
   if (indicators == NULL) {
	   fprintf (stderr, "Error: standard function malloc has failed\n");
	   status=1;
	   goto TERMINATE;
   }
   CPXsolution(p_env, p_lp, &status, score, indicators, NULL, NULL, NULL);
   buildClusters(gr, indicators, avgWeightBetweenClusters, avgWeightWithinClusters);

TERMINATE:
   if ( p_lp != NULL ) {
      status = CPXfreeprob (p_env, &p_lp);
      if ( status ) {
         fprintf (stderr, "Error: CPXfreeprob failed, error code %d.\n", status);
      }
   }

   if ( p_env != NULL ) {
      status = CPXcloseCPLEX (&p_env);
      if ( status ) {
         char  errmsg[1024];
         fprintf (stderr, "Could not close CPLEX environment.\n");
         CPXgeterrorstring (p_env, status, errmsg);
         fprintf (stderr, "%s", errmsg);
      }
   }
   return (status);
}

/*
 * The function builds the clusters of the graph based on the the results of CPLEX placed in the edgeIndicators array.
 * It also populates avgWeightBetweenClusters, avgWeightWithinClusters according to CPLEX, which indicates whether an edge is
 * crossing clusters or within a certain cluster.
 */
int buildClusters(graph* gr, double* edgeIndicators, double* avgWeightBetweenClusters, double* avgWeightWithinClusters){
	clusterInfo* cluster = NULL;
	vertexQueue* vQueue = NULL;
	vertexQueueItem* vertexCursor=NULL;
	edgeListItem* edgeCursor = NULL;
	int i, status;
	int* discoveredVerticesArr = NULL;
	calcEdgesStatistics(gr, edgeIndicators, avgWeightBetweenClusters, avgWeightWithinClusters, 1);
	status=divideToClusters(gr, edgeIndicators);
	if (status == ERROR){
		goto TERMINATE_CLUSTERS;
	}
	vQueue = malloc(sizeof(vertexQueue));
	if (vQueue == NULL){
		fprintf (stderr, "Error: standard function malloc has failed\n");
		status=ERROR;
		goto TERMINATE_CLUSTERS;
	}
	vQueue->head = vQueue->last = NULL;
	discoveredVerticesArr = calloc(gr->numofVertices, sizeof(int));
	if (discoveredVerticesArr == NULL){
		fprintf (stderr, "Error: standard function malloc has failed\n");
		status = -1;
		goto TERMINATE_CLUSTERS;
	}
	/* Run BFS for each vertex in the graph to get the diameter of each cluster */
	for (i=0;i<gr->numofVertices;i++){
		memset(discoveredVerticesArr, 0, gr->numofVertices*sizeof(int)); /* Reset discovered vertices */
		enqueueIfNotDiscovered(vQueue, discoveredVerticesArr, gr->vertices[i], 0);
		while (vQueue->head != NULL){
			vertexCursor = dequeueVertex(vQueue);
			edgeCursor = vertexCursor->vertexData->edges->head;
			if (!edgeCursor)
				continue;
            if(!edgeCursor -> edgeData -> isDeleted)
            {
            	enqueueIfNotDiscovered(vQueue, discoveredVerticesArr, edgeCursor->edgeData->vertex1, vertexCursor->distance+1);
            	enqueueIfNotDiscovered(vQueue, discoveredVerticesArr, edgeCursor->edgeData->vertex2, vertexCursor->distance+1);
            }
			edgeCursor = edgeCursor->next;
			while (edgeCursor != vertexCursor->vertexData->edges->head){
                if(!edgeCursor -> edgeData -> isDeleted)
                {
                	enqueueIfNotDiscovered(vQueue, discoveredVerticesArr, edgeCursor->edgeData->vertex1, vertexCursor->distance+1);
                	enqueueIfNotDiscovered(vQueue, discoveredVerticesArr, edgeCursor->edgeData->vertex2, vertexCursor->distance+1);
                }
				edgeCursor = edgeCursor->next;
			}
			cluster = vertexCursor->vertexData->cluster;
			cluster->diameter =	cluster->diameter<=vertexCursor->distance ? vertexCursor->distance : cluster->diameter;
		}
	}
	for (i=0;i<gr->numOfEdges;i++){
		/* Calculate cluster score*/
        if(!gr -> edges[i] -> isDeleted)
		gr->edges[i]->vertex1->cluster->score+=gr->edges[i]->weight;
	}
	for (i=0;i<gr->numofVertices;i++){
		if(gr->vertices[i]->cluster->size > 1 && gr->vertices[i]->degree==0){
			/*If there's a vertex with no edges in a cluster with size > 1 then the diameter is infinite*/
			gr->vertices[i]->cluster->diameter = INT_MAX;
		}
	}

	qsort(gr->clusters, gr->numOfClusters, sizeof(clusterInfo*), comparator);
	for (i=0;i<gr->numOfClusters;i++){
		gr->clusters[i]->id = i+1;
	}

TERMINATE_CLUSTERS:
   freeVertexQueue(vQueue);
   free(discoveredVerticesArr);
   return status;
}

/*
 * The function calculates the average weight of crossing edges and cluster edges. It removes crossing edges if remove crossing edges != 0
 */
void calcEdgesStatistics(graph* gr, double* edgeIndicators, double* avgWeightBetweenClusters, double* avgWeightWithinClusters, int removeCrossingEdges){
	double**  adjMatrix =NULL;
	int i,j;
	int indicatorCounter=0, numofClusterEdges=0, numofCrossingEdges=0;
	double sumofCrossingEdges = 0, sumOfClusterEdges = 0;
	adjMatrix = getAdjMatrix(gr);

	for (i=0;i<gr->numofVertices-1;i++){
		for (j=i+1;j<gr->numofVertices;j++){
			if (adjMatrix[i][j] != -gr->defaultWeigth){
				if (IS_VALUE_1(edgeIndicators[indicatorCounter])){
					numofClusterEdges++;
					sumOfClusterEdges+=adjMatrix[i][j];
				} else {
					numofCrossingEdges++;
					sumofCrossingEdges+=adjMatrix[i][j];
					if (removeCrossingEdges){
						removeEdge(gr, i, j);
					}
				}
			}
            indicatorCounter++;
		}
	}

	*avgWeightBetweenClusters = numofCrossingEdges == 0 ? 0 : sumofCrossingEdges / numofCrossingEdges;
	*avgWeightWithinClusters = numofClusterEdges == 0 ? 0 : sumOfClusterEdges / numofClusterEdges;
	free(adjMatrix);
}

/*
 * Divide the graph into clusters (populate the cluster field of each vertex) and set the cluster sizes.
 */
int divideToClusters(graph* gr, double* edgeIndicators){
	int i, j, variableIndex;
	clusterInfo* cluster;
	for (i=0;i<gr->numofVertices-1;i++){
		for (j=i+1;j<gr->numofVertices;j++){
			variableIndex = getVariableIndexFromVertices(gr, i, j);
			if (IS_VALUE_1(edgeIndicators[variableIndex])){
				if (gr->vertices[i]->cluster==NULL){
					cluster = malloc(sizeof(clusterInfo));
					if(cluster == NULL)
					{
						fprintf (stderr, "Error: standard function malloc has failed\n");
						return ERROR;
					}
					cluster->id = gr->numOfClusters;
					cluster->diameter=0;
					cluster->size=1;
					cluster->score=0;
					addCluster(gr, cluster);
					gr->vertices[i]->cluster = cluster;
				}
				if (gr->vertices[j]->cluster == NULL){
					gr->vertices[j]->cluster = gr->vertices[i]->cluster;
					gr->vertices[j]->cluster->size++;
				}
			}
		}
	}
	for (i=0;i<gr->numofVertices;i++){
		if (gr->vertices[i]->cluster==NULL){
			cluster = malloc(sizeof(clusterInfo));
			if(cluster == NULL)
			{
				fprintf (stderr, "Error: standard function malloc has failed\n");
				return ERROR;
			}
			cluster->id = gr->numOfClusters;
			cluster->diameter=0;
			cluster->size=1;
			cluster->score=0;
			addCluster(gr, cluster);
			gr->vertices[i]->cluster = cluster;
		}
	}
	return OK;
}
